/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-08-14
 * Time: 22:54
 */

/**
 * 复写零:
 *
 * 给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
 *
 * 注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。
 *
 *
 *
 * 示例 1：
 *
 * 输入：arr = [1,0,2,3,0,4,5,0]
 * 输出：[1,0,0,2,3,0,0,4]
 * 解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]
 * 示例 2：
 *
 * 输入：arr = [1,2,3]
 * 输出：[1,2,3]
 * 解释：调用函数后，输入的数组将被修改为：[1,2,3]
 *
 * 提示：
 * 1 <= arr.length <= 104
 * 0 <= arr[i] <= 9
 */
public class Exercise {

    public void duplicateZeros(int[] arr) {
        //1从前向后，先找第一次复写的位置，
        /**
         找复写的位置的方法：
         1.先判断cur的值，再决定dest走一步或者两步
         2.判断des是否到结束位置,结束就跳出循环
         3.cur++
         */
        //注意特殊情况cur最后指向0;让dest-=2; n-1位置复写为0
        int dest = -1;
        int cur = 0;
        int n = arr.length;

        while(cur < n) {
            if(arr[cur] == 0) {
                dest += 2;
            }else {
                dest += 1;
            }
            if(dest >= n-1){
                break;
            }

            cur++;
        }


        //2.从后向前复写

        //处理特殊情况->越界
        if(dest == n) {
            arr[n-1] = 0;
            dest -= 2;
            cur--;
        }

        copy(arr,cur,dest);

    }

    //2.从后向前复写
    private void copy (int[] array,int cur,int dest) {
        for(int i = cur; i >= 0; i--){
            if(array[i] != 0) {
                array[dest--] = array[i];
            }else {
                array[dest--] = array[i];
                array[dest--] = array[i];
            }
        }
    }
}
